Log-structured storage systems may be used as a storage component in a distributed database management system. On a conventional storage system, data is changed by locating the existing data on a storage device and overwriting it. A log-structured storage system, on the other hand, may operate by appending a description of the changes to the end of a log file that describes a series of changes to the data. Log-structured storage systems may be efficient for scenarios that involve numerous updates, at least in part because existing data does not need to be located or overwritten.
One characteristic of log-structured storage systems is that they are not necessarily space efficient. Because data is not overwritten when it is changed, previous versions of data may consume a significant amount of storage space. Log-structured storage systems may perform coalescing and truncation operations as a technique for improving space utilization. Coalescing involves applying a sequence of changes to an object to a baseline version of the object, producing a subsequent version of the object that can be used as a new baseline. Truncation involves deleting or otherwise removing descriptions of changes that occurred prior to the new baseline. To realize the latest version of an object, a series of log entries may be traversed, starting with the most recent baseline. However, due to truncation, versions of the object prior to the new baseline are no longer realizable in this manner.